package junior.Recursion递推;

public class 数组三角形普通 {
    static int N = 5;
    static int[][] orignal = {
            {7,0,0,0,0},
            {3,8,0,0,0},
            {8,1,0,0,0},
            {2,7,4,4,0},
            {4,5,2,6,5}}; // 组合数学的思想，寻找边界，左右走的不差1
    public static void main(String[] args) {
        int a[][] = new int[N][N];
        // a赋值
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                a[i][j] = orignal[i][j];
            }
        }
        // 限制条件
        for (int i = N- N/2; i < N; i++) {
            for (int j = 0; j < 3-(N-i); j++) {
                a[i][j] = 0;
            }
            for (int j = N- N/2; j < i+1; j++) {
                a[i][j] = 0;
            }
        }
        for (int j = 0; j <N; j++) {
            System.out.print(a[N-1][j]+"\t");
        }
        System.out.println();
        // 求最大值
        for (int i = N-2; i >=0; i--) {
            for (int j = 0; j <= i; j++) {
                a[i][j] += Math.max(a[i+1][j],a[i+1][j+1]);
            }
            for (int j = 0; j <= i; j++) {
                System.out.print(a[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println();
        System.out.print("路径：");
        int i = 0,j=0;
        for (; i < N-1;i++) {
            System.out.print(a[i][j] -Math.max(a[i+1][j],a[i+1][j+1]) + "\t");
            if(a[i+1][j] < a[i+1][j+1])
                j=j+1;
        }
        System.out.println(a[i][j] + "\t");
        System.out.println("最大值："+ a[0][0]);
    }
}
